#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>
void sys_err(char* str){
    perror(str);
}

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* swapNodes(struct ListNode* head, int k){
    struct ListNode* cur = head;
    struct ListNode* parr[10000] = {head};
    int OrderIndex;
    int ReverseIndex;
    int index = 0;
    if (head == NULL ){//空链表
        return NULL;
    }
    while (cur->next != NULL){//存在下一个节点，记录所有节点的地址
        parr[++index] = cur->next;
        cur = cur->next;
    }
    if (k == 1 && index == 0)//只有一个节点
        return head;
    OrderIndex = (k-1)<(index+1-k)?(k-1):(index+1-k);//正数的第k个元素，下标为k-1 
    ReverseIndex = (k-1)<(index+1-k)?(index+1-k):(k-1);//逆数的第k个元素，下标为最后一个元素的下标-k+1
    cur = parr[ReverseIndex];//指向逆数第k个地址
    if ((k == 1 || k == index+1) && index >= 2){//交换末尾的节点,且元素大于两个
        head = cur;//此时的尾节点通过交换位置变为首节点
        cur->next = parr[OrderIndex+1];//尾巴指向正数第二个节点
        cur = parr[OrderIndex];//断开第一个节点和第二个节点的联系，使它成为尾节点
        cur->next = NULL;
        cur = parr[ReverseIndex-1];//拼接原来的首节点
        cur->next = parr[OrderIndex];
        return head;//返回新的首节点
    }
    if (k == 1 || k == index+1){//交换末尾的节点,且元素等于二
        head = cur;
        cur->next = parr[OrderIndex];
        cur = parr[OrderIndex];
        cur->next = NULL;
        return head;
    }
    if (index%2 == 0 && k == index/2+1 )//返回中间元素
        return head;
    if ( (index+1)%2 ==0 && (k == (index+1)/2 || k == (index+1)/2+1)){//交换相邻元素
       cur->next = parr[OrderIndex];
       cur = parr[OrderIndex-1];
       cur->next = parr[ReverseIndex];

       cur = parr[OrderIndex];
       cur->next = parr[ReverseIndex+1];

       return head;
    }
    cur->next = parr[OrderIndex+1];
    cur = parr[OrderIndex-1];
    cur->next = parr[ReverseIndex];

    cur = parr[OrderIndex];
    cur->next = parr[ReverseIndex+1];
    cur = parr[ReverseIndex-1];
    cur->next = parr[OrderIndex];
    return head;
}

void ShowList(struct ListNode* phead){//打印链表函数，直接copy上次作业的
    struct ListNode* cur = phead;
    if (cur == NULL)
        printf("空链表");
    else{
        while (cur->next != NULL )//不是尾节点，打印；尾节点，结束打印
        {
            printf("%d ",cur->val);
            cur = cur->next;
        }   printf("%d\n",cur->val);//打印尾节点内部的内容,顺便还行
    }
}

int main(int argc,char* argv[]){
    //    struct ListNode N5 = {5, NULL};
    struct ListNode N4 = {4, NULL};
    struct ListNode N3 = {3, &N4};
    struct ListNode N2 = {2, &N3};
    struct ListNode N1 = {1, &N2};
    struct ListNode* head = &N1;
    struct ListNode* cur= &N1;
    head = swapNodes(head, 2); 
    ShowList(head);
}
